package problem;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class S_102 {
    //二叉树的层次遍历
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
    //DFS
    class Solution1{
        List<List<Integer>> levels=new ArrayList<>();
        public void helper(TreeNode node,int level){
            if(levels.size()==level) levels.add(new ArrayList<>());
            levels.get(level).add(node.val);
            if(node.left!=null) helper(node.left,level+1);
            if(node.right!=null) helper(node.right,level+1);
        }
        public List<List<Integer>> levelOrder(TreeNode root) {
            if(root==null) return levels;
            helper(root,0);
            return levels;
        }
    }

    //BFS
    class Solution{
        public List<List<Integer>> levelOrder(TreeNode root){
            List<List<Integer>> levels=new ArrayList<>();
            if(root==null) return levels;
            Queue<TreeNode> queue=new LinkedList<>();
            queue.add(root);
            int level=0;
            while (queue.isEmpty()){
                levels.add(new ArrayList<>());
                int level_len=queue.size();
                for(int i=0;i<level_len;i++){
                    TreeNode node=queue.remove();
                    levels.get(level).add(node.val);
                    if(node.left!=null) queue.add(node.left);
                    if(node.right!=null) queue.add(node.right);
                }
                level++;
            }
            return levels;
        }
    }
}
